package com.company.algo.graph;

import com.company.algo.debugUtils.DebugUtils;

public class pathSum {
    int res = 0;
    int target;
    //求路径个数，回溯法
    public int numWays(int n, int[][] relation, int k) {
        int start = 0;
        target = n - 1;
        int[][] graph = new int[n][n];
        for(int[] edge: relation){
            graph[edge[0]][edge[1]] = 1;
        }
        DebugUtils.printMatrix(graph);
        dfs(start, graph, k);
        return res;
    }
    public void dfs(int start, int[][] graph, int k){
        if(k==0){
            if(start == target) res +=1;
            return;
        }
        for(int i = 0; i < graph[start].length; i++){
            if (graph[start][i] == 1)
                dfs(i, graph, k-1);
        }
    }

    public static void main(String[] args) {
        pathSum Main = new pathSum();
        int n = 5;
        int[][]relations = new int[7][2];
        relations[0] = new int[]{0,2};
        relations[1] = new int[]{2,1};
        relations[2] = new int[]{3,4};
        relations[3] = new int[]{2,3};
        relations[4] = new int[]{1,4};
        relations[5] = new int[]{2,0};
        relations[6] = new int[]{0,4};
        System.out.println(Main.numWays(n, relations, 3));
    }
}
